package team6.gametree;

import team6.AI.Player;
import team6.gamegui.GameState;

import java.util.*;


/**
 * Contains all the methods and data needed to build a min/max game tree and return the best
 * move.  This can cause a out of memory or heap space error if depth is set too deep: with no
 * or little pruning maximum depth is 5.
 * 
 * 
 * @author Drew Havard
 * @author Drew Reagan
 */
public class UtilityTree {
	/**
	 * Private wrapper class for the nodes of the utility tree
	 * Has a vector of children, the move that was performed last
	 * and the utility of the gameState the node represents
	 * 
	 * @author Drew Havard
	 * @author Drew Reagan
	 *
	 */
	class UtilityNode{
		/**
		 * The utility for the gameState the node is representing.
		 * Can be positive or negative.
		 */
		double utility;
		/**
		 * A two dimensional array of the move in the form {row, column}.
		 */
		int[] move;
		/**
		 * A Vector of all of the direct children.
		 * null if no children
		 */
		Vector<UtilityNode> children;
		/**
		 * Construct a new utility node.
		 * 
		 * 
		 * @param inUtility		This parameter assigned to member variable utility
		 * @param inMove		This parameter is assigned to member variable move. 
		 * 						This is a shallow copy.
		 * @param inChildren	This parameter is assigned to member 
		 * 						variable children.  This is a shallow copy.
		 */
		public UtilityNode(double inUtility, int[] inMove, Vector<UtilityNode> inChildren){
			utility = inUtility;
			move = inMove;
			children = inChildren;
		}
	}
	/**
	 * Pointer to base utilityNode of the tree
	 */
	UtilityNode root;
	/**
	 * The depth of the tree to be constructed.  With little to no pruning max recommended depth is 5.
	 */
	int depth;
	/**
	 * The player who is building the tree, and therefore the AI calling this function, is designated to be positive.
	 */
	Player positive;
	/**
	 * Constants for the utilityFunction
	 * Format is: 1st constant is value of pieces
	 * 2nd constant is value of opponent moves (usually negative)
	 * 3rd constant is value of corners
	 */
	double utilityConstants[];
	/**
	 * Using in pruning for recursion method.  Is the constant
	 * multiplied by the value of pieces from utilityConstants[0].  A
	 * higher number means that pruning will happen more and the algorithm
	 * will run faster, but more good nodes could be ignored.  Default 
	 * value is 2, given from testing of algorithm.
	 */
	double pruningConstant;
	
	
	/**
	 * Constructs a new utilityTree, but does NOT build it.
	 * buildTree must be called to actually make the tree.
	 * 
	 * @param inDepth				int:  The maximum level or depth of the tree
	 * @param inUtilityConstants	double[]:  Constants for the utilityFunction
	 * 								Format is: 1st constant is value of pieces
	 * 								2nd constant is value of opponent moves (usually negative)
	 * 								3rd constant is value of corners
	 */
	public UtilityTree(int inDepth, double inUtilityConstants[]){
		depth = inDepth;
		utilityConstants = inUtilityConstants;
		pruningConstant = 2;
	}

    /**
     * Changes the depth of the search. 
     * 
     * @param newdepth	int: The new recursive depth search. Should 
     * 					be an odd number >=3
     */
    public void changeDepth(int newdepth) {
        depth=newdepth;
    }
    
    public void setPruningConstant(double inPruningConstant){
    	pruningConstant = inPruningConstant;
    }

    /**
     * Gets the current recursive search depth
     * 
     * @return int: Returns depth member variable
     */
    public int getDepth() {
        return depth;
    }

	
	/**
	 * Given an certain state, will build a min/max tree.
	 * The depth of the tree is based off of the depth variable
	 * 
	 * @param currentState	GameState: Represents the state of the base of the tree
	 */
	public void buildTree(GameState currentState){
		positive = currentState.currentPlayer();
		root = recursion(0, currentState, new Vector<int[]>(), utilityFunction(currentState));
	}
	
	/**
	 * Searched through the root node children for the best move, decided by highest utility
	 * 
	 * @return  int[]: Returns the best int[] move for the root node
	 */
	public int[] bestMove(){
		double utility = Double.MIN_VALUE;
		int[] move = {-1, -1};
		for(UtilityNode node: root.children)
			if(node.utility > utility || utility == Double.MIN_VALUE){
				utility = node.utility;
				move = node.move;
			}
		return move;
	}
	
	/**
	 * Change the constants for the utiliyFunction
	 * Useful for AI's that will dynamically change the utilityFunction
	 * 
	 * @param inUtilityConstants	double[]:  Constants for the utilityFunction
	 * 								Format is: 1st constant is value of pieces
	 * 								2nd constant is value of opponent moves (usually negative)
	 * 								3rd constant is value of corners
	 */
	public void updateConstants(double[] inUtilityConstants){
		utilityConstants = inUtilityConstants;
	}
	
	/**
	 * This function is used to recursively build the tree.  It implements pruning, and on most machines
	 * can build a tree five levels deep in near real time.  Changing the pruning constant can make this algorithm
	 * move drastically faster, but can also cause it to ignore moves that might be better if processed to full
	 * depth.
	 * 
	 * @param currentLevel	int: The current level of the tree.  Starts at 0 and progresses to depth
	 * @param originalState	GameState: Represents a pointer to the original gamestate.
	 * 						The GameState is not changed throughout this method, it is cloned and then
	 * 						the copies are changed.
	 * @param inMoves		Vector<int[]>:  Since the originalState is never changed, this represents all
	 * 						of the moves since the original state to get to the current state.
	 * @param inUtility		double:  The utility of the parent node.  Used in pruning checks.
	 * @return				UtilityNode:  Built at the end of the method, either ending a branch of the
	 * 						tree or constructed after recursion is called for all direct and indirect children
	 * 						of this node.
	 */
	private UtilityNode recursion(int currentLevel, GameState originalState, Vector<int[]> inMoves, double inUtility){
		String gameOver = originalState.gameOver();
		if(currentLevel == depth || !gameOver.equals("")){
			int[] lastMove = {-1, -1};
			double utility = 0;
			if(gameOver.equalsIgnoreCase("Black"))
				if(positive == Player.BLACK)
					utility = Integer.MAX_VALUE;
				else
					utility = Integer.MIN_VALUE;
			else{
				if(gameOver.equalsIgnoreCase("White"))
					if(positive == Player.WHITE)
						utility = Integer.MAX_VALUE;
					else
						utility = Integer.MIN_VALUE;
				else
					if(gameOver.equalsIgnoreCase("Tie"))
						utility = 0;
					else{  //If gameOver is ""
						GameState childState = (GameState) originalState.clone();
						for(int[] past: inMoves){
							childState.moveNoGui(past[0], past[1]);
							childState.switchTurn();
						}
						lastMove = childState.getLastMove();
						utility = utilityFunction(childState);
					}
			}
			return new UtilityNode(utility, lastMove, null);
		}
		GameState childState = (GameState) originalState.clone();
		for(int[] past: inMoves){
			childState.moveNoGui(past[0], past[1]);
			childState.switchTurn();
		}
		double utility = utilityFunction(childState);
		int lastMove[] = childState.getLastMove();
		if(currentLevel > 0){
            if(childState.currentPlayer() != positive){
                    if(cornerThisTurn(childState))
                            return new UtilityNode(10000, lastMove, null);
                    else
                            if(inUtility >utility + (pruningConstant * utilityConstants[0]) && depth > 3)
                                    return new UtilityNode(inUtility, lastMove, null);
            } else
                    if(cornerThisTurn(childState))
                            return new UtilityNode(-10000, lastMove, null);
                    else
                            if(utility > inUtility + (pruningConstant * utilityConstants[0]) && depth > 3)    
                                    return new UtilityNode(inUtility, lastMove, null);
		}

		Vector<UtilityNode> children = new Vector<UtilityNode>();
		for(int[] childMove: childState.possibleMoves()){
			inMoves.add(childMove);
			children.add(recursion(currentLevel + 1 , originalState, inMoves, utility));
			inMoves.remove(inMoves.lastElement());
            if (utility==Double.MIN_NORMAL)
                utility=children.lastElement().utility;
            else if(childState.currentPlayer() == positive){
				if(children.lastElement().utility > utility)
					utility = children.lastElement().utility;
			} else
				if(children.lastElement().utility < utility)
					utility = children.lastElement().utility;
		}
		
		UtilityNode current = new UtilityNode(utility, lastMove, children);
		return current;
		
	}
	/**
	 * Given the current state calculates the utility
	 * 
	 * @param currentState	GameState: State utility is calculated from.  This
	 * 						does not change in this method.
	 * @return				double:  Utility for the given function.  Can be positive
	 * 						or negative.
	 */
	public double utilityFunction(GameState currentState){
		double calcUtility = utilityConstants[0]*(currentState.numPiecesCurrentPlayer()) + utilityConstants[1]*(currentState.possibleMoves().size()) +
				utilityConstants[2] * currentState.numCorners();
		if(currentState.currentPlayer() != positive)
			return calcUtility;
		else
			return -calcUtility;
	}
	
	
	/**
	 * Determines whether or not a corner was taken during the last move for the given state
	 * 
	 * @param currentState	GameState: State that the method will work on.  This
	 * 						does not change in this method.
	 * @return				boolean:  Returns whether or not the last
	 */
	public boolean cornerThisTurn(GameState currentState){
        int[] lastMove = currentState.getLastMove();
        if(lastMove[0] == 0){
                if(lastMove[1] == 0 || lastMove[1] == 7)
                        return true;
        }else if(lastMove[0] == 7)
                if(lastMove[1] == 0 || lastMove[1] == 7)
                        return true;
        return false;
        }

}
